package com.cqs.leetcode.recursion;

/**
 * @author lixqw
 * @date 2020/9/5
 */
public class KthSymbolGrammar779 {

    public int kthGrammar(int N, int K) {
        if (K <= 2) return K - 1;
        //“父”节点所在的位置　＝＝> 通过(N-1,pos)　生成(N,K)
        int pos = kthGrammar(N - 1, (K + 1) / 2);
        //＝＝１表示第１个元素。注意这里１是首个元素
        return K % 2 == 1 ? pos : 1 ^ pos;
    }


    /**
     * 内存溢出
     */
    static class Solution {
        private StringBuilder sb = null;

        public int kthGrammar(int N, int K) {
            kthGrammar(N, 1, new StringBuilder("0"));
            return sb.charAt(K - 1) - '0';
        }

        private void kthGrammar(int N, int level, StringBuilder pre) {
            if (level == N) {
                sb = pre;
                return;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < pre.length(); i++) {
                char c = pre.charAt(i);
                if (c == '0') {
                    sb.append("01");
                } else {
                    sb.append("10");
                }
            }
            kthGrammar(N, level + 1, sb);
        }
    }


    public static void main(String[] args) {
        KthSymbolGrammar779 sk = new KthSymbolGrammar779();
        Solution so = new Solution();

        sk.kthGrammar(3, 1);
        for (int j = 1; j < 29; j++) {
            int N = j;
            for (int i = 0; i < (2 << N); i++) {
                int K = 1;
                int i0 = sk.kthGrammar(N, K);
                int i2 = so.kthGrammar(N, K);
                if (i0 != i2) {
                    System.out.println(N + "\t" + K + "\t" + i0 + "\t" + i2);
                    break;
                }
            }
        }


    }
}
